1. Field of Use
The present invention relates to tables and table search techniques and, more particularly, to an efficient organization of a hash table and corresponding techniques for accessing the hash table that are especially useful in multi-threaded environments.
2. State of the Related Art
In the computer sciences, various data structures, table organizations and access techniques have been studied in an effort to solve what may generally be referred to as the "searching problem." The term "searching problem" is used here to refer to the problem of locating a particular item of information that has been stored along with others in some fashion.
In the prior art, it has been recognized that the particular choice of an algorithm/data structure depends on the nature of the storage medium (internal memory, magnetic tape, disk, or other), on the nature of the data being organized, and on the requirements of the search (e.g., must the search be tailored to be fast on average, or is one concerned more with the worst case performance).
In general, the data may be stored into a table of "n" elements, where each element has a collection of fields associated with it. In the table, each field is associated with one of a number of attributes that, together, make up the element. One of the attributes is the "key" that refers to the element and on which the searching is based. Various techniques for organizing a table include lists, binary search trees, digital search trees and hash tables. The remainder of this disclosure will focus exclusively on hash tables.
A number of hash table techniques are well-known in the art. What these techniques have in common is that an element is stored in a table location that is computed directly from the key of the element. That is, the key is provided as an input to a hash function, h, which transforms the key into an index into the table. If the location of the table addressed by the index (represented here as T[index]) is empty, then the element may be stored there. If it is not empty, then a "collision" has occurred, and further techniques must be applied to find an empty location in which to store the element. It can be seen, then, that the properties of the hash table are determined, at least in part, by the hash function and the collision resolution method. Under certain circumstances, a hash table may be the best choice for organizing data, because the average times for a search can be made arbitrarily close to constant by allocating sufficient memory for the table.
Hashing techniques may be categorized as being either "open hashing" or "closed hashing." In principle, open hashing techniques permit the size of the table to grow indefinitely because the index generated by the hash function points to one of a number of classes, called "buckets", into which the element will be stored. Thus, each bucket comprises a list of elements. By constructing the list as a "linked list", those having ordinary skill in the art will recognize that the table size may be virtually unbounded.
In contrast to open hashing schemes, the number of entries that can be stored into a closed hash table cannot exceed a predefined number, which designates the size of the table. Because of this limitation, open hashing techniques may generally be preferred. However, several properties of the closed hash table make it advantageous under certain circumstances. One of these properties is the fact that one need not store, at each entry, a pointer to a next entry. Instead, conventional closed hashing techniques require that each element include only the key and value fields. Consequently where the size of the table is an important design consideration, a closed hash table may be preferred.
Furthermore, a closed hash table may provide better speed performance if the table is to be accessed by means of a hardware cache. Cache techniques are well-known. Very briefly, a computer architecture may include a slower, large main memory, and a faster, smaller hardware cache memory. In operation, the data used by a program is stored in the main memory. When the processor desires to retrieve a particular data item, it first looks for that item in the cache. If the data is not found (called a "cache miss"), then the data item is sought and retrieved from the main memory. In recognition of the fact that programs tend to read and write data that are stored at addresses that are close to one another in memory (referred to as the "locality principle"), whenever a cache miss occurs, the desired data item as well as a predefined number of "nearby" items (as determined by address) are retrieved from the main memory and loaded into the cache. As a result, the next attempt that the processor makes to retrieve a data item from the cache will likely result in success (referred to as a "cache hit"), obviating the need for the subsequent step of accessing main memory.
Because the collision resolution techniques employed in a closed hash table usually result in the data item being stored at a location that is at least close to the location designated by the index value, a processor is less likely to take multiple cache misses when attempting to access the table. Thus, where a hardware cache is employed, the closed hash table may be preferred over the open hash table, whose buckets may include elements that are widely distributed throughout the available address space.
It is known that a hash table can be shared by a number of concurrently operating threads of execution, which will henceforth be referred to throughout this specification as "threads." Such concurrent operation may result from each thread being assigned to a corresponding one of a number of processors in a multi-processor environment. Alternatively, logical concurrence may be achieved by an operating system using "time slice" techniques on only a single processor ("uni-processor").
When a hash table is to be shared by two or more threads, efficiency becomes a critical issue because it is often necessary to deny table access to all but one of the threads in the system if the table is to provide accurate insert, delete and lookup operations. For example, if Thread1 were permitted to store two characters, "AB" while Thread2 were concurrently storing the two characters "CD" to the same table location, one possible outcome would be that Thread1 would get as far as storing the first character "A," at which time Thread2 might store its two characters "CD." When Thread1 subsequently completes its operation by storing the final character "B," the resulting stored data, "CB", is a character string that was stored by neither thread.
Conventional solutions for ensuring that every thread has a consistent view of information in the shared hash table require severe forms of concurrency control which can detrimentally affect system performance due to excessive contention for access to the shared environment. For example, any of a number of well-known concurrency control locking strategies (henceforth referred to as "locks") may be applied to serialize the occurrence of table lookup, insert and delete operations. That is, one thread's access to the hash table is permitted, while all other threads are required to wait their turn. If the duration of the lockout is for any appreciable amount of time, a waiting thread in a time-sliced uni-processor system may be forced, by its operating system, to relinquish other system resources that it has acquired. Consequently, when that thread is subsequently granted access to the hash table, it may be forced to waste even more time reacquiring those resources which had been relinquished. In multi-processor systems, a thread that is waiting for a lock to become available may simply be left waiting, without any useful work being performed by the thread's processor. Consequently, reducing locking in this situation is very important for achieving good scalability.
One hash table operation that may be relatively time-consuming involves the deletion of a stored element from a closed hash table. This is because one cannot simply locate the element to be deleted and then mark it "empty" because doing so would disrupt the probe sequence for elements that collided with the one to be deleted. Therefore, it is further necessary, in some deletion algorithms, to have the additional capability of marking an element as "deleted." A location that has been marked as "deleted" acts like an empty location with respect to insertions, but like a full location with respect to searches.
However, marking a table location as "deleted" has a drawback in that search times will not improve after a deletion. That is, if the table becomes substantially full at some point, searches will never become more efficient no matter how many entries are deleted after that. One method of addressing this problem is by performing a process called "rehashing," in which each table location is scanned in turn and its contents, if any, are relocated as necessary. Because this process is time-consuming, it is not performed after every delete, but is instead scheduled only periodically in conventional practice.
Another method of improving the search efficiency of the table after a delete is described by D. Knuth in The Art of Computer Programming, Volume III: Sorting and Searching, 1972, Reading, Mass. There, a method is taught in which each delete comprises first locating the element to be deleted, then marking this first location as "empty", and then scanning subsequent locations in turn for an element whose probe sequence has been disrupted by the first "empty" location. This element, if any, is then moved into the first empty location, and the newly vacated location is then marked as "empty." The process then continues to identify and move any other elements whose probe sequences have been disrupted by the introduction of a new empty location, and these are similarly moved. The process ends when an already existing empty location is found. It can be seen that, if the table becomes relatively full, deletion of an element may require more and more time as a result of the necessity of initially marking many locations as "empty," followed by movement of other elements into those temporarily "empty" locations.
Because a great proportion of data processing involves the need to store and search for data elements, it is desirable to provide techniques that allow for even greater efficiency than is conventionally known, both in uni- and multi-threaded environments.